#define _CRT_SECURE_NO_WARNINGS 1

#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> cmp;
        for (auto& e : words)
        {
            cmp[e]++;
        }
        int length = words[0].size();
        for (int i = 0; i < length; ++i)
        {
            unordered_map<string, int> hash;
            for (int left = i, right = i + length, count = 0; right <= s.size(); right += length)
            {
                string tmp1(s, right - length, length);
                if (cmp.count(tmp1) && hash[tmp1]++ < cmp[tmp1]) ++count;
                string tmp2(s, left, length);
                while (right - left > words.size() * length)
                {
                    if (cmp.count(tmp2) && hash[tmp2]-- <= cmp[tmp2]) --count;
                    left += length;
                }
                if (count == words.size()) ret.push_back(left);
            }
        }
        return ret;
    }
};